//class Solution {
//public:
//    int thirdMax(vector<int>& nums) {
//        set<int> s(nums.begin(), nums.end());
//        int fir = INT_MIN, sec = INT_MIN, thr = INT_MIN;
//        for (auto x : s)
//        {
//            if (x > fir) thr = sec, sec = fir, fir = x;
//            else if (x > sec) thr = sec, sec = x;
//            else if (x > thr) thr = x;
//        }
//        if (s.size() <= 2) return fir;
//        else return thr;
//    }
//};



//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int ret = 0;
//        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
//        {
//            if (nums[right] == 0) zero++;
//            while (zero > k)
//            {
//                if (nums[left++] == 0) zero--;
//            }
//            ret = max(right - left + 1, ret);
//        }
//        return ret;
//    }
//};





//class Solution {
//public:
//    int ListLen(ListNode* head)
//    {
//        int len = 0;
//        ListNode* cur = head;
//        while (cur)
//        {
//            len++;
//            cur = cur->next;
//        }
//        return len++;
//    }
//    ListNode* reverseKGroup(ListNode* head, int k) {
//        int len = ListLen(head);
//        ListNode* newhead = new ListNode(), * prev = newhead, * cur = head;
//        for (int i = 0; i < len / k; i++)
//        {
//            ListNode* tmp = cur;
//            for (int j = 0; j < k; j++)
//            {
//                ListNode* next = cur->next;
//                cur->next = prev->next;
//                prev->next = cur;
//                cur = next;
//            }
//            prev = tmp;
//        }
//        prev->next = cur;
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




//class Solution {
//public:
//    class Comp
//    {
//    public:
//        bool operator()(const ListNode* l1, const ListNode* l2)
//        {
//            return l1->val > l2->val;
//        }
//    };
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
//        for (auto& list : lists)
//        {
//            if (list != nullptr) pq.push(list);
//        }
//
//        ListNode* newhead = new ListNode(0), * prev = newhead;
//        while (!pq.empty())
//        {
//            ListNode* top = pq.top();
//            pq.pop();
//
//            prev->next = top;
//            prev = prev->next;
//            if (top->next) pq.push(top->next);
//        }
//        prev->next = nullptr;
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




//class Solution {
//public:
//    vector<vector<int>> levelOrder(Node* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr) return ret;
//        queue<Node*> q;
//        q.push(root);
//        while (!q.empty())
//        {
//            int sz = q.size();
//            vector<int> cur;
//            for (int i = 0; i < sz; i++)
//            {
//                Node* top = q.front();
//                q.pop();
//
//                cur.push_back(top->val);
//                for (auto node : top->children)
//                {
//                    q.push(node);
//                }
//            }
//            ret.push_back(cur);
//        }
//        return ret;
//    }
//};



class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size();
            vector<int> cur;
            for (int i = 0; i < sz; i++)
            {
                Node* top = q.front();
                q.pop();

                cur.push_back(top->val);
                for (auto node : top->children)
                {
                    q.push(node);
                }
            }
            ret.push_back(cur);
        }
        return ret;
    }
};